We study PAC learning in tabular discounted Markov decision processes with exogenous i.i.d. contexts, with discount factor $γ$, finite state space $\mathcal X$, action space $\mathcal A$, and context space $\mathcal Z$. At each time step, a context is drawn independently from an unknown distribution $μ$ and revealed before the agent acts. This context may affect both rewards and transitions, while remaining uncontrolled by the agent. Depending on the regime, the learner has access either to a sampling oracle for $μ$, to a sampling oracle for the transition kernel conditioned on state-context-action tuples, or to both. Oracles can be accessed before and during policy execution. The sample complexity is measured by a couple $(n,m)$, where $n$ is the number of calls to the sampling oracles before execution and $m$ is the number of calls to the sampling oracles during execution. When rewards and transitions are known and only the context distribution $μ$ is sampled, we give a variance-reduced algorithm that solves policy evaluation (PE), best-value estimation (BVE), and best-policy extraction (BPE) with $\left(\widetilde O\left(1/((1-γ)^3\varepsilon^2)\right), 0 \right) $ sample complexity. The rate is independent of $|\mathcal Z|$ and minimax optimal up to logarithmic factors. As a corollary, we also obtain tight rates in the case of one-step perfect look-ahead, improving upon the existing guarantees. In the fully unknown regime, where both $μ$ and P must be learned, we show that PE remains $|\mathcal Z|$-free, with matching upper and lower bounds $\bigl(\widetilde O(|\mathcal X|/((1-γ)^3\varepsilon^2)),\, \widetilde O(1/((1-γ)^2\varepsilon^2))\bigr)$.

We first need the following lemma, which bounds the prediction shifts and magnitudes of Algorithm 2. See proof in Appendix A.2. We are now ready to prove Theorem 9. Proof of Theorem 9. We show that Algorithm 2 achieves the desired regret bound. Lipschitz) where the last transition used the Lipschitz assumption to bound the gradient. This concludes the second part of the lemma. We give a general example of a BCO algorithm that may be employed in conjunction with our reduction procedure given in Algorithm 2. For a positive semi-definite matrix Moreover, for all null null we have that 1. if null The proof of Lemma 15 relies on a few standard results.

We first need the following lemma, which bounds the prediction shifts and magnitudes of Algorithm 2. See proof in Appendix A.2. We are now ready to prove Theorem 9. Proof of Theorem 9. We show that Algorithm 2 achieves the desired regret bound. Lipschitz) where the last transition used the Lipschitz assumption to bound the gradient. This concludes the second part of the lemma. We give a general example of a BCO algorithm that may be employed in conjunction with our reduction procedure given in Algorithm 2. For a positive semi-definite matrix Moreover, for all null null we have that 1. if null The proof of Lemma 15 relies on a few standard results.

We thank the reviewers for their careful consideration and their feedback, our replies are provided below. We will add a conclusion section to summarize our paper. NLD is indeed a bit unfortunate but the name "non-reversible" for such dynamics is We will define it earlier than Line 114. We thank the reviewer for the insightful comments. We sincerely apologize for mis-citing Lemma EC.6 in [GGZ18].

We then select those that yield the best convergence performance. However, our code supports GPU cluster training. VRBO becomes slower and less stable. As a result, single-sample based algorithms enable a larger parameter update per sample, and hence achieve a higher sample efficiency. Besides, we apply the standard grid search for the inner-and outer-loop stepsizes for all algorithms.

The exact minimum width that allows for universal approximation of unbounded-depth networks is known only for ReLU and its variants. In this work, we study the minimum width of networks using general activation functions. Specifically, we focus on squashable functions that can approximate the identity function and binary step function by alternatively composing with affine transformations. We show that for networks using a squashable activation function to universally approximate $L^p$ functions from $[0,1]^{d_x}$ to $\mathbb R^{d_y}$, the minimum width is $\max\{d_x,d_y,2\}$ unless $d_x=d_y=1$; the same bound holds for $d_x=d_y=1$ if the activation function is monotone. We then provide sufficient conditions for squashability and show that all non-affine analytic functions and a class of piecewise functions are squashable, i.e., our minimum width result holds for those general classes of activation functions.

Consider a group $G$ of order $M$ acting unitarily on a real inner product space $V$. We show that the sorting based embedding obtained by applying a general linear map $\alpha : \mathbb{R}^{M \times N} \to \mathbb{R}^D$ to the invariant map $\beta_\Phi : V \to \mathbb{R}^{M \times N}$ given by sorting the coorbits $(\langle v, g \phi_i \rangle_V)_{g \in G}$, where $(\phi_i)_{i=1}^N \in V$, satisfies a bi-Lipschitz condition if and only if it separates orbits. Additionally, we note that any invariant Lipschitz continuous map (into a Hilbert space) factors through the sorting based embedding, and that any invariant continuous map (into a locally convex space) factors through the sorting based embedding as well.